class Solution {
public:
    long long minimumCost(int m, int n, vector<int>& horizontalCut, vector<int>& verticalCut) {
        // 逆向思维：从 6 个 1 * 1 的蛋糕开始，合并成 1 个 3 * 2 的大蛋糕
        // 把 1 x 1 的蛋糕视作节点，把合并视作连边
        // 由于我们不会把已经合并在一起的蛋糕重复合并，所以上述过程是不会形成环的。
        // 换句话说，我们得到的是一棵树，一棵生成树
        // 切蛋糕的最小总开销，最小生成树的边权之和

        // 根据最小生成树的 Kruskal 算法，先把边权从小到大排序，然后遍历边，如果边的两个点属于不同连通块，则合并
        // 一般地，我们用双指针计算答案：
        // 从小到大排序两个数组。初始化 i = j = 0
        ranges::sort(horizontalCut);
        ranges::sort(verticalCut);
        int i = 0, j = 0;

        // 如果 horizontalCut[i] < verticalCut[j]，把 n − j 条边权为 horizontalCut[i] 的边加入答案，然后 i++
        // 否则，把 m − i 条边权为 verticalCut[j] 的边加入答案，然后 j++
        // 循环次数为两个数组的长度之和，即 (m − 1) + (n − 1) = m + n − 2
        int t = m + n - 2;
        long long ans = 0;
        // while(t--)
        while(i < m - 1 || j < n - 1)
        {
            if(j == n - 1 || i < m - 1 && horizontalCut[i] < verticalCut[j])    // 每次选择小的边
            {
                ans += horizontalCut[i++] * (n - j);
            }
            else
            {
                ans += verticalCut[j++] * (m - i);
            }
        }
        return ans;
    }
};